package com.lw.leetcode.back.b;

/**
 * create by idea
 * 79. 单词搜索
 * 剑指 Offer 12. 矩阵中的路径
 *
 * @author lmx
 * @version 1.0
 * @date 2021/11/28 19:31
 */
public class Exist {

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean b = find(board, word, i, j, 0);
                if (b) {
                    return b;
                }
            }
        }
        return false;
    }

    private static boolean find(char[][] board, String word, int x, int y, int index) {
        int m = board.length;
        int n = board[0].length;
        if (x < 0 || x == m) {
            return false;
        }
        if (y < 0 || y == n) {
            return false;
        }
        char c = board[x][y];
        if (c == '0') {
            return false;
        }
        boolean flag = false;
        if (c == word.charAt(index)) {
            index++;
            if (word.length() == index) {
                return true;
            }
            board[x][y] = '0';
            flag = find(board, word, x, y + 1, index)
                    || find(board, word, x, y - 1, index)
                    || find(board, word, x + 1, y, index)
                    || find(board, word, x - 1, y, index);
            board[x][y] = c;
        }
        return flag;
    }

}
